这次回顾第二周的内容。

课程主页：https://www.coursera.org/learn/analysis-of-algorithms

Exercise

2.17

Solve the recurrence $A_{N}=A_{N-1}-\frac{2 A_{N-1}}{N}+2\left(1-\frac{2 A_{N-1}}{N}\right) \quad \text { for } N>0 \text { with } A_{0}=0$.

This recurrence describes the following random process: A set of $N$ elements collect into “2-nodes” and “3-nodes.” At each step each 2-node is likely to turn into a 3-node with probability $2/N$ and each 3-node is likely to turn into two 2-nodes with probability $3/N$ What is the average number of 2-nodes after $N$ steps?

解：对递推式进行处理可得

两边同除

可得

记

所以原递推式即为（$N\ge 6$）

化简可得（$N\ge 6$）

2.69

Plot the periodic part of the solution to the recurrence $a_{N}=3 a_{\lfloor N / 3\rfloor}+N \quad \text { for } N>3 \text { with } a_{1}=a_{2}=a_{3}=1$ for $1 \leq N \leq 972$.

解：利用主定理可得

所以周期项为

编程并作图可得

代码如下：

import numpy as np
import matplotlib.pyplot as plt

N = 973
a = np.zeros(N)
a[1:4] = 1

for n in range(4, N):
    a[n] = 3 * a[n // 3] + n
    
index = np.arange(1, N)
b = index * np.log(index) / np.log(3)
res = b - a[1:]

#作图
plt.plot(index, res)
plt.show()

Problem

1

Suppose that $a_{n}=2 a_{\lfloor n / 3\rfloor} + n \text { for } n>2 \text { with } a_{0}=a_{1}=a_{2}=1$. What is the order of growth of $a_n$?

  • $\Theta\left(n^{3}\right)$
  • $\Theta\left(n^{2}\right)$
  • $\Theta(n \log n)$
  • $\Theta(n)$

解：

因为

所以增长速度为

2

Which of the following is true of the number of comparisons used by Mergesort?

  • Has periodic behavior
  • Order of growth is $N \lg N$
  • Exactly $N \lg N$ when $N$ is a power of $2$
  • Is less than $N \lg N + N/4$ for all $N$

答案为全选，参考课件第38页。

3

Suppose that $n a_{n}=(n-3) a_{n-1}+n$ for $n>2$ with $a_{0}=a_{1}=a_{2}=0$. What is the value of $a_{999}$?

解：

两边除以

得到

记

所以原递推式即为

解得

因此

所以